package main

// 抓住两条性质
// a ^ 0 = a    作用： 可以统计列表中只出现一次的元素（其他元素出现两次）
// a ^ a = 0
// 参考第「136. 只出现一次的数字」 这道题， 这里是用巧妙的方法，将 这个问题 转化为 求 136的问题
// 所有数字进行异或， 得到的结果就是 x ^ y  x异或y的 结果。  找到第一位为 1的结果（假设为j位置）， 说明 x， y 中一位为 0， 另一位 为 1
// 而出现两次的数字， 都在同一边， 所以划分好两边之后（按照j位置为1 或 0 划分）
// 分别进行两次异或，就可以求出结果了！
func singleNumber(nums []int) []int {
	// 先求出 x^y 的结果
	xorSum := 0
	for _, num := range nums {
		xorSum ^= num
	}
	// 求第一位为 1的位置
	lsb := xorSum & -xorSum
	x, y := 0, 0
	for _, num := range nums {
		if num & lsb > 0 {   // 区分开两类
			x ^= num
		} else {
			y ^= num
		}
	}

	return []int{x, y}
}